public class Solution {

    /**
     * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
     *
     * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
     * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
     * 那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，
     * 那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
     *
     * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
     * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
     * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
     * 给你一个整数数组 nums ，找出 nums 的下一个排列。
     *
     * 必须 原地 修改，只允许使用额外常数空间。
     *
     */
    public void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        if (nums.length == 2) {
            int tmp = nums[0];
            nums[0] = nums[1];
            nums[1] = tmp;
            return;
        }

        int end = nums.length - 1;
        int cur = end - 1;
        int perMax = nums[end];

        while (cur >= 0) {
            int value = nums[cur];
            if (perMax > value) {
                int point = findPoint(nums, value);
                int tmp = nums[cur];
                nums[cur] = nums[point];
                nums[point] = tmp;

                turn(nums, cur+1, nums.length-1);
                return;
            }
            perMax = value;
            cur--;
        }

        turn(nums, 0, nums.length-1);
    }

    private int findPoint(int[] nums, int value) {
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > value) {
                return i;
            }
        }
        return 0;
    }

    private void turn(int[] nums, int start, int end) {
        int tmp = 0;
        while (start < end) {
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

}
